package divide;

import object.SubArrayObj;

/**
 * 最大子数组
 */
public class SubArrayMax {


  public  static void main(String args[]){

      int num[]=new int[]{-10,-2,-7,-10,11,-1,-3,10,20,-8,-1,0,-10};

      // 递归求最大子数组
      SubArrayObj result1=findMaxSubArray(num,0,num.length-1);
      System.out.println("递归求最大子数组:"+result1);
      //线性求最大子数组（暴力法）
      SubArrayObj result2=lineMaxSubArray(num,0,num.length-1);
      System.out.println("线性求最大子数组（暴力法）:"+result2);
      //线性求最大子数组（暴力法）
      SubArrayObj result3=lineMaxSubArray2(num,0,num.length-1);
      System.out.println("线性求最大子数组（比暴力法更快）:"+result2);
  }

    /**
     * 线性求最大子数组（暴力法）
     * @param num
     * @param left
     * @param right
     * @return
     */
    public static SubArrayObj lineMaxSubArray(int[] num,int left,int right){

      int maxLeft=0;
      int maxRight=0;
      int sumMax=-9999;//设置哨兵
      int sum=0;
      for(int i=left;i<=right;i++){
          sum=sum+num[i];
          if(sum>sumMax){
              maxLeft=i;
              sumMax=sum;
              maxRight=i;
          }

          for(int j=i+1;j<=right;j++){
              sum=sum+num[j];
              if(sum>sumMax){
                  maxLeft=i;
                  sumMax=sum;
                  maxRight=j;
              }
          }
          sum=0;
      }
    return  new SubArrayObj(maxLeft,maxRight,sumMax);
    }


    /**
     * 线性求最大子数组2（比暴力法快）
     * @param num
     * @param left
     * @param right
     * @return
     */
    public static SubArrayObj lineMaxSubArray2(int[] num,int left,int right){

        int sum=-99999;
        int maxSum=-99999;
        int maxLeft=0;
        int maxRight=0;
        int currentLeft=0;
        int currentRight=0;

        for(int i=left;i<=right;i++){
           currentRight=i;
           if(sum>0){
               sum=sum+num[i];
           }
           else{
                sum=num[i];
                currentLeft=i;
           }
           if(sum>maxSum){
                maxLeft=currentLeft;
                maxRight=currentRight;
                maxSum=sum;
           }

        }
        return new SubArrayObj(maxLeft,maxRight,maxSum);
    }

    /**
     * 递归求最大子数组
     * @param num
     * @param left
     * @param right
     * @return
     */
  public static SubArrayObj findMaxSubArray(int[] num,int left,int right){

      if(left==right){
          return new SubArrayObj(left,right,num[left]);
      }
      int mid=(left+right)/2;
      SubArrayObj leftObj=findMaxSubArray( num, left, mid);
      SubArrayObj rightObj=findMaxSubArray( num, mid+1, right);
      SubArrayObj crossingObj=findMaxCrossingSubArray( num, left,mid,right);
      if(leftObj.getSum()>=rightObj.getSum() && leftObj.getSum()>=crossingObj.getSum()){
          return leftObj;
      }
      else if(rightObj.getSum()>=leftObj.getSum() && rightObj.getSum()>=crossingObj.getSum()){
          return rightObj;
      }
     else return crossingObj;
  }

  public static SubArrayObj findMaxCrossingSubArray(int[] num,int left,int mid,int right){

      int leftSum=0;
      int rightSum=0;
      boolean leftFlag=true; //首次进入左边区间的判断标志
      boolean rightFlag=true; //首次进入右边区间的判断标志
      int sum=0;
      int maxLeft=0;
      int maxRight=0;
      //左区别计算
      for(int i=mid;i>=left;i--){
          if(leftFlag){
                sum=sum+num[i];
                leftSum=sum;
                maxLeft=i;
                leftFlag=false;
          }
          else{
                sum=sum+num[i];
                if(sum>leftSum){
                    leftSum=sum;
                    maxLeft=i;
                }
          }
      }
      //右区别计算
      sum=0;
      for(int i=mid+1;i<=right;i++){
          if(rightFlag){
              sum=sum+num[i];
              rightSum=sum;
              maxRight=i;
              rightFlag=false;
          }
          else{
              sum=sum+num[i];
              if(sum>rightSum){
                  rightSum=sum;
                  maxRight=i;
              }
          }
      }
      return new SubArrayObj(maxLeft,maxRight,leftSum+rightSum);
  }


}
